from math import floor,sqrt
from fractions import Fraction
'''思路主要参考：http://www.cnblogs.com/qiu520/p/3730290.html'''

aaa = 9      #记录最大的值
maxD = 5        #记录产生最大值的D值
n = range(2,1001)#1000以下

for D in n:
    if int(sqrt(D))**2==D:
        continue
    list0 = []
    s = 0 #记录周期
    b = 0
    c = 1
    r = (sqrt(D)+b)/c
    a = a0 = floor(r)
    while a != 2 * a0:#循环计算根号D的连分式
        '''  √2=[1;(2)], period=1
            √3=[1;(1,2)], period=2
            √5=[2;(4)], period=1
            √6=[2;(2,4)], period=2
            √7=[2;(1,1,1,4)], period=4
            √8=[2;(1,4)], period=2
            √10=[3;(6)], period=1
            √11=[3;(3,6)], period=2
            √12= [3;(2,6)], period=2
            √13=[3;(1,1,1,1,6)], period=5'''
        a = floor(r)
        list0.append(a)
        b = c * a - b
        c = int((D-b**2)/c)
        r = (sqrt(D) + b) / c
        s += 1

    sums = 0
    for n in list0[-2::-1]:
        sums = Fraction(1, n + sums)
    if (s-1)%2 != 0:
        #如果是奇数，要转换为p，q后再计算特解
        p = sums.denominator
        q = sums.numerator
        sums = Fraction(2*p*q,2*(p**2)+1)

    print("D=%d对应的两个值（%d,%d）" % (D, sums.denominator,sums.numerator))
    if sums.denominator>=aaa:
        aaa = sums.denominator
        maxD = D
        print("==================================")
        print('目前最大的值是（%d,%d）'%(aaa,maxD))
        print("==================================")

print("1000以下最小的X最大的是%d,使得其最大的D是:%d" % (aaa, maxD))